package com.congee02;

public class ShortestBeautifulSubstring_Prefix_Enum {

    public String shortestBeautifulSubstring(String s, int k) {

        char[] cs = s.toCharArray();

        int n = cs.length;

        int pre = 0;
        int[] pres = new int[n];

        for (int i = 0 ; i < n ; i ++ ) {
            pres[i] = (pre += (cs[i] - '0'));
        }

        String ans = "";
        int minL = Integer.MAX_VALUE;
        for (int i = 0 ; i < n ; i ++ ) {
            for (int j = i + k - 1; j < n ; j ++ ) {
                if (range(pres, i, j) == k) {
                    int rangeLength = j - i + 1;
                    if (rangeLength < minL) {
                        ans = s.substring(i, j + 1);
                        minL = rangeLength;
                    } else if (rangeLength == minL) {
                        String cur = s.substring(i, j + 1);
                        if (cur.compareTo(ans) < 0) {
                            ans = cur;
                        }
                    }
                }
            }
        }

        return ans;
    }

    private int range(int[] pres, int l, int r) {
        return pres[r] - (l > 0 ? pres[l - 1] : 0);
    }

}
